\documentclass{ctexart}
\usepackage{lmodern} % choose a font that is available as T1,消除字体大小差异警告
\usepackage{amsmath} % 支持数学公式排版常用宏包
\usepackage{hyperref} % 自动生成PDF书签,需要多次编译运行
\usepackage[T1]{fontenc}% specify encoding
\usepackage{textcomp} % load symbol definitions
\title{一维动态规划}
\author{Albert Darren}
\date{\today}
\begin{document}
\maketitle
\tableofcontents
\newpage
\section{拾取硬币}
\subsection{问题引入}
假如有n个硬币排在一行，如：
$$c[0],c[1],\dots ,c[n-1]$$

要求不能拾取相邻的两个硬币，以获得累加面值最大的拾取子序列。比如，有面值如下的硬币：
$$5,1,2,10,6,2$$

可以拾取5+2+6=13，也可以拾取1+10+2=13。以上两种拾取的硬币均不相邻，因此都是符合要求的拾取方式。但是，最大总面值的拾取应是5+10+2=17。这个拾取首先没有相邻的硬币，而且是所有可行拾取中累加面值最大的一个拾取。

以上问题最直接的算法是求出所有可行的拾取子序列，并求出它们各自的累加值，其中累加值最大的序列就是所求结果。也就是，从输入序列中穷举所有可行序列。由于序列中每一个元素要么在所求序列中，要么不在，这样将有$2^n$个可行序列。因此，采用穷举法来求解该问题的算法效率是指数规模，下面将介绍通过动态规划来获得一个更为高效的算法。
\subsection{定义子问题}

不妨设从硬币$c[0]$直到$c[i]$中累加和最大的值为$collect\_coins(i)$.如果将每一个硬币都当成一个字符，输入硬币的前缀$c[:i]$就是定义的子问题，该子问题的求解函数示为$collect\_coins()$。由于$i$取值$[0,n-1]$，因此子问题的个数为$n$。
\subsection{猜测解}

利用动态规划求解斐波那契数时，由于直接给出了斐波那契数的递归式，因此并不需要猜测解这一步。然而，当利用动态规划求解大部分问题时，都需要我们构建问题的递归解。为了求得子问题的解，就需要使用猜测这一方法。猜测就是一种尝试或者假设。
对于子问题$c[:i]$，考察硬币$c[i]$，它存在两种可能的猜测：
\begin{itemize}
    \item 最优解不包括第$i$个硬币。那么前i个硬币累加和最大值应等于$collect\_coins(i-1)$
    \item 最优解包括第$i$个硬币。那么前i个硬币累加和最大值则等于$collect\_coins(i-2)+c[i]$
\end{itemize}

在子问题$c[:i]$的解中，我们考察硬币$c[i]$。对于$c[i]$，不妨先猜测最优解中不包括硬币$c[i]$，则子问题$c[:i-1]$的解等于子问题$c[:i]$的解。比如c=[5，1，
2，10，6]，该子问题的解为5+10=15，最后的硬币6不在最优解中，那么将硬币6拿开后剩余的子问题为$c[:i-1]$=[5，1，2，10]，这个子问题的解依然是5+10=15。

此外，硬币$c[i]$也可能就在最优解中，那么子问题$c[:i]$的解应等于子问题$c[:i-2]$的解加上硬币$c[i]$的面值。比如，子问题$c[:i]$=[5，1，2，10]，其最优解为5+10=15。硬币10在最优解中，那么子问题$c[:i-2]$=[5，1]的最优解为5，因此子问题$c[:i]$| 的最优解15等于子问题c|:i-2]的最优解5加上$c[i]$=10。
\subsection{子问题之间的递归关系}
% 根据以上分析，不难得到子问题之间的递归关系：
\begin{align}
    collect \underline{~~} coins(i)=max\{c[i-1]+collect \underline{~~} coins(i-2),collect \underline{~~} coins(i-1),i \geqslant 2\} \label{子问题递归关系}
\end{align}

该递归式表明$collect\_coins(i)$要么等于$collect\_coins(i-1)$，要么等于 $collect\_coins(i-2)+c[i-1]$。由于原问题是求最大的累加面值，因此$collect\_coins(i)$的值应该等于它们之中较大的那个。当没有硬币时，$collect_coins()=0$。只有一个硬币的话，$collect_coins()$应该等于当前的硬币面值。因此，式\ref{子问题递归关系}的边界条件为，
\begin{align}
    collect \underline{~~} coins(0)=0,collect \underline{~~} coins(1)=c[0]
\end{align}
递归式\ref{子问题递归关系}存在诸多重复的子问题，如$collect\_coins(1),collect\_coins(2), collect\_coins(3)$等。此外，还存在优化的子结构，也就是原问题的最优解可由各个子问题的最优解合成得到。这意味着如果采用自底向上的方法实现递归式\ref{子问题递归关系}，可以获得较高的执行效率。
\subsection{自底向上构造动态规划表}

建立了子问题间的递归关系，就可以利用自底向上的方法求解递归关系。自底向上实现递归的本质就是填表，我们称该表为动态规划表。一个子问题就对应于表格的一个单元格，每一个单元格的值经由递归式来完成计算。因此，单元格在计算过程中存在相互依赖关系。

为了保证动态规划表内每一个单元格在计算过程中都有足够的数据，因此填表的过程必须满足拓扑排序。也就是说，表中某个单元的值只依赖于已有值的单元格。

\end{document}
